package _07_matrixGraph;

import _05_matrix.Matrix;
import _05_triple.Triple;
import _07_abstractGraph.AbstractGraph;

public class MatrixGraph<T> extends AbstractGraph<T> {
    
    // 矩阵对象，存储图的邻接矩阵
    protected Matrix matrix;
    
    // 构造空图，定点数为0，边数为0
    public MatrixGraph() {
        super();
        // 构造0x0矩阵，默认容量
        this.matrix = new Matrix(0, 0);
    }
    
    // 以vertexes顶点集合构造图，边集合为空
    public MatrixGraph(T[] vertexes) {
        this();
        for (int i = 0; i < vertexes.length; i++) {
            // 插入顶点
            this.insert(vertexes[i]);
        }
    }
    
    // 以vertexes顶点集合和edges边集合构造图
    public MatrixGraph(T[] vertexes, Triple[] edges) {
        // 以vertexes顶点集合构造图，没有边
        this(vertexes);
        for (int i = 0; i < edges.length; i++) {
            // 插入边
            this.insert(edges[i]);
        }
    }
    
    public int insert(T x) {
        // TODO Auto-generated method stub
        // 顶点顺序表尾插入x，自动扩容
        this.vertexlist.insert(x);
        // 获得插入顶点x的序号
        int i = vertexlist.size() - 1;
        // 若邻接矩阵容量不够，i >= matrix.getRows() 等价于 vertexlist.size() > getRows()
        if (i >= matrix.getRows()) {
            matrix.setRowsColumns(i+1, i+1);
        }
        // 初始化第i行/列元素值为∞。i==j值已为0
        for (int j = 0; j < i; j++) {
            matrix.set(i, j, MAX_WEIGHT);
            matrix.set(j, i, MAX_WEIGHT);
        }
        return i;
    }

    // 插入边<vi, vj>，权值为w
    public void insert(int i, int j, int w) {
        // TODO Auto-generated method stub
        if (i != j) {
            if (w < 0 || w > MAX_WEIGHT) {
                w = MAX_WEIGHT;
            }
            this.matrix.set(i, j, w);
        } else {
            throw new IllegalArgumentException("不能插入自身环，i = " + i + "，j = " + j);
        }
    }
    
    public void insert(Triple edge) {
        // TODO Auto-generated method stub
        insert(edge.getRow(), edge.getColumn(), edge.getValue());
    }
    
    // 返回图的顶点集合和邻接矩阵描述字符串
    public String toString() {
        String str = super.toString() + "邻接矩阵：\n";
        // 顶点数
        int n = this.vertexCount();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (this.matrix.get(i, j) == MAX_WEIGHT) {
                    str += "     ∞";
                } else {
                    str += String.format("%6d", this.matrix.get(i, j));
                }
            }
            str += "\n";
        }
        return str;
    }
    
    // 删除边<vi, vj>，将该值
    public void remove(int i, int j) {
        // TODO Auto-generated method stub
        if (i != j) {
            // 设置边的权值为∞，set方法中对i, j容错
            this.matrix.set(i, j, MAX_WEIGHT);
        }
    }
    
    // 删除顶点vi及其所有关联的边，返回顶点vi元素。用最后一个顶点替换顶点vi
    public T remove(int i) {
        // TODO Auto-generated method stub
        // 原顶点数
        int n = this.vertexCount();
        // 最后一个顶点
        T x = this.vertexlist.get(n-1);
        if (i >= 0 || i < n) {
            
            // 将第i个顶点用最后一个顶点代替
            this.vertexlist.set(i, x);
            // 删除最后一个顶点（顶点数-1）
            x = this.vertexlist.remove(n-1);
            // 将第i行替换为第n-1行，注意n还是原顶点数，那么下面for循环条件可以换成n-1吗？
            for (int j = 0; j < n-1; j++) {
                if (i == j) {
                    break;
                }
                // 将第i行替换为第n-1行
                this.matrix.set(i, j, this.matrix.get(n-1, j));
                // 将第i列替换为第n-1列
                this.matrix.set(j, i, this.matrix.get(j, n-1));
            }
            /*
            for (int j=i+1; j<n; j++)                      //第i+1～n-1行元素上移一行，n为原顶点数
                for (int k=0; k<n; k++)
                    this.matrix.set(j-1, k, this.matrix.get(j,k));
            for (int j=0; j<n; j++)
                for (int k=i+1; k<n; k++)                  //第i+1～n-1列元素左移一列
                    this.matrix.set(j, k-1, this.matrix.get(j,k));
            */
            this.matrix.setRowsColumns(n-1, n-1);
        } else {
            throw new IndexOutOfBoundsException("i = " + i);
        }
        return x;
    }
    
    @Override
    // 返回<vi, vj>边的权值
    public int weight(int i, int j) {
        // TODO Auto-generated method stub
        // 返回矩阵[i, j]值，对i, j容错
        return this.matrix.get(i, j);
    }
    
    @Override
    // 返回顶点vi在vj后的后继邻接顶点（不包括vj）；若j = -1，则返回vi第一个邻接顶点序号；
    // 若不存在后继邻接顶点，则返回-1
    protected int next(int i, int j) {
        // TODO Auto-generated method stub
        int n = this.vertexCount();
        if (i >= 0 && i < n && j >= -1 && j < n) {
            // 当j = -1时，那么从0索引开始搜寻后继邻接顶点
            for (int k = j + 1; k < n; k++) {
                // 如果有边
                int weight = this.matrix.get(i, k);
                // System.out.println(k + ", " + weight);
                if (weight > 0 && weight < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }
    
    @Override
    public void minSpanTree() {
        // TODO Auto-generated method stub
        
    }

    @Override
    public void shortestPath(int i) {
        // TODO Auto-generated method stub
        
    }

    @Override
    public void shortestPath() {
        // TODO Auto-generated method stub
        
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // 带权无向图G3的顶点集合
        String[] vertexes = {"A", "B", "C", "D", "E", "F"};
        // G3的边集合
        Triple[] edges = {
                new Triple(0, 1, 45), new Triple(0, 2, 28), new Triple(0, 3, 10),
                new Triple(1, 0, 45), new Triple(1, 2, 12), new Triple(1, 4, 21),
                new Triple(2, 0, 28), new Triple(2, 1, 12),
                new Triple(3, 0, 10),
                new Triple(4, 1, 21)};
        // 邻接矩阵存储的图
        MatrixGraph<String> graph = new MatrixGraph<String>(vertexes, edges);
        System.out.println("带权无向图G3，" + graph.toString());
        System.out.println("测试remove(int i, int j)：");
        graph.remove(1, 0);
        System.out.println(graph.toString());
        System.out.println("测试remove(int i)：");
        System.out.println(graph.remove(2));
        System.out.println(graph.toString());
        System.out.println("测试next(int i, int j)：");
        System.out.println(graph.next(3, -1));
        System.out.println("测试DFSTraverse(int i)：");
        MatrixGraph<String> graph1 = new MatrixGraph<String>(vertexes, edges);
        graph1.DFSTraverse(0);
        System.out.println("测试BFSTraverse(int i)：");
        graph1.BFSTraverse(0);
        Triple[] edges1 = {
                new Triple(0, 1, 45), new Triple(0, 2, 28), new Triple(0, 3, 10),
                new Triple(1, 0, 45), new Triple(1, 2, 12), new Triple(1, 4, 21),
                new Triple(2, 0, 28), new Triple(2, 1, 12), new Triple(2, 3, 17), new Triple(2, 4, 26),
                new Triple(3, 0, 10), new Triple(3, 2, 17), new Triple(3, 4, 15), new Triple(3, 5, 13),
                new Triple(4, 1, 21), new Triple(4, 2, 26), new Triple(4, 3, 15), new Triple(4, 5, 11),
                new Triple(5, 3, 13), new Triple(5, 4, 11)};
        MatrixGraph<String> graph2 = new MatrixGraph<String>(vertexes, edges1);
        System.out.println(graph2);
        graph2.DFSTraverse(0);
        graph2.BFSTraverse(0);
    }
}
